package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.cn/problems/maximum-count-of-positive-integer-and-negative-integer/'>正整数和负整数的最大计数(Maximum Count of Positive Integer and Negative Integer)</a>
 * <p>
 * 给你一个按 非递减顺序 排列的数组 nums ，返回正整数数目和负整数数目中的最大值。
 *     <ul>
 *         <li>换句话讲，如果 nums 中正整数的数目是 pos ，而负整数的数目是 neg ，返回 pos 和 neg二者中的最大值。</li>
 *     </ul>
 * </p>
 * <p>注意：0 既不是正整数也不是负整数。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：nums = [-2,-1,-1,1,2,3]
 *      输出：3
 *      解释：共有 3 个正整数和 3 个负整数。计数得到的最大值是 3 。
 *
 * 示例 2：
 *      输入：nums = [-3,-2,-1,0,0,1,2]
 *      输出：3
 *      解释：共有 2 个正整数和 3 个负整数。计数得到的最大值是 3 。
 *
 * 示例 3：
 *      输入：nums = [5,20,66,1314]
 *      输出：4
 *      解释：共有 4 个正整数和 0 个负整数。计数得到的最大值是 4 。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= nums.length <= 2000</li>
 *     <li>-2000 <= nums[i] <= 2000</li>
 *     <li>nums 按 非递减顺序 排列。</li>
 * </ul>
 * </p>
 * <b>进阶：你可以设计并实现时间复杂度为 O(log(n)) 的算法解决此问题吗？</b>
 *
 * @author c2b
 * @since 2024/4/9 14:09
 */
public class LC2529MaximumCountOfPositiveIntegerAndNegativeInteger_S {

    static class Solution {
        public int maximumCount(int[] nums) {
            // 在非递减排列的数组nums中：
            // 1.查找第一个大于等于0的元素的下标，则该下标即为负整数的数目
            // 2.查找第一个大于等于1的元素的下标，所有元素 - 该下标即为正整数的数目
            return Math.max(search(nums, 0), nums.length - search(nums, 1));
        }

        /**
         * 在非递减排列的数组nums中查找第一个大于等于target的元素的下标
         *
         * @param nums   非递减排列的数组
         * @param target 目标值
         * @return 非递减排列数组中的第一个大于等于target的元素的下标
         */
        private int search(int[] nums, int target) {
            int left = 0;
            int right = nums.length;
            while (left < right) {
                int mid = left + ((right - left) >> 1);
                if (nums[mid] >= target) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            return left;
        }

        public int maximumCount2(int[] nums) {
            int pos = 0;
            int neg = 0;
            for (int num : nums) {
                if (num > 0) {
                    ++pos;
                } else if (num < 0) {
                    ++neg;
                }
            }
            return Math.max(pos, neg);
        }
    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.maximumCount(new int[]{-2, -1, -1, 1, 2, 3}));
        System.out.println(solution.maximumCount(new int[]{-3, -2, -1, 0, 0, 1, 2}));
        System.out.println(solution.maximumCount(new int[]{5, 20, 66, 1314}));
    }
}
